package 数组;

/**
 * 寻找两个正序数组的中位数
 *
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 */

public class L4_difficult {

    public static void main(String[] args) {

        int[] nums1 = new int[]{1,3};
        int[] nums2 = new int[]{2};
        double medianSortedArrays = findMedianSortedArrays(nums1, nums2);
        System.out.println(medianSortedArrays);
    }

    /**
     * 解题思路：
     *      首先，因为两个数组的长度都是已知的，故中位数的位置也是知道的，为了时间复杂度最低，遍历长度较少的那个数组
     *      其次，满足中位数条件
     *          1、线左边的数都小于右边的数：nums1[midA-1] < nums2[midB] && nums1[midA] > nums2[midB-1]
     *          2、如果不满足中位数条件，切线的位置就需要调整
     *      最后，如果中位线已经找到的话，如果长度为奇数 那么中位数就是 max(nums1[midA-1], nums2[midB-1])
     *      如果长度为偶数 那么中位数就是(max(nums1[midA-1], nums2[midB-1]) + min(nums1[midA], nums2[midB])) / 2
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;

        // 控制nums1的长度是最小的
        if (length1 > length2) return findMedianSortedArrays(nums2, nums1);

        int low = 0, high = nums1.length, mid = (totalLength + 1) / 2, nums1Mid = 0, nums2Mid = 0;

        while (low <= high) {
            nums1Mid = low + ((high-low) / 2);
            nums2Mid = mid - nums1Mid;
            if (nums1Mid > 0 && nums1[nums1Mid - 1] > nums2[nums2Mid]) {
                high = nums1Mid - 1;
            } else if (nums1Mid != length1 && nums1[nums1Mid] < nums2[nums2Mid - 1]) {
                low = nums1Mid + 1;
            } else {
                break;
            }
        }

        double midLeft = 0, midRight = 0;
        if (nums1Mid == 0) {
            midLeft = nums2[nums2Mid - 1];
        } else if (nums2Mid == 0) {
            midLeft = nums1[nums1Mid - 1];
        } else {
            midLeft = Math.max(nums1[nums1Mid - 1], nums2[nums2Mid - 1]);
        }

        if (totalLength % 2 == 1) return midLeft;

        if (nums1Mid == length1) {
            midRight = nums2[nums2Mid];
        } else if (nums2Mid == length2) {
            midRight = nums1[nums1Mid];
        } else {
            midRight = Math.min(nums1[nums1Mid], nums2[nums2Mid]);
        }

        return (midLeft + midRight) / 2;

    }

}
